home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / BOOL-HI.C < prev    next >
C/C++ Source or Header  |  1992-01-28  |  17KB  |  490 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *   Module to handle the high level Boolean operations. The other modules    *
  7. * should only call this module to perform Boolean operations. All the        *
  8. * operations are none-destructives, meaning the given data is not modified.  *
  9. *   Note all the polygons of the two given objects must be convex, and the   *
  10. * returned object will also have only convex polygons!                 *
  11. *****************************************************************************/
  12.  
  13. /* #define DEBUG        If defined, return intersection polyline object. */
  14.  
  15. #ifdef __MSDOS__
  16. #include <alloc.h>
  17. #endif /* __MSDOS__ */
  18.  
  19. #include <stdio.h>
  20. #include <ctype.h>
  21. #include <math.h>
  22. #include <string.h>
  23. #include <signal.h>
  24. #include "program.h"
  25. #include "allocate.h"
  26. #include "attribut.h"
  27. #include "booleang.h"
  28. #include "booleanl.h"
  29. #include "convex.h"
  30. #include "ctrl-brk.h"
  31. #include "graphgen.h"
  32. #include "matherr.h"
  33. #include "objects.h"
  34. #include "windows.h"
  35.  
  36. int BooleanOutputInterCurve = FALSE;    /* Kind of output from Boolean oper. */
  37.  
  38. static jmp_buf LclLongJumpBuffer;         /* Used in fatal Boolean error. */
  39. static int FatalErrorType,             /* Type of fatal Boolean error. */
  40.        BooleanOperation;           /* One of BooleanOR, BooleanAND, etc. */
  41.  
  42. static ObjectStruct *BooleanCombineTwoObjs(ObjectStruct *PObj1,
  43.                        ObjectStruct *PObj2);
  44. static ObjectStruct *VerifyBooleanInput(ObjectStruct *PObj1,
  45.                     ObjectStruct *PObj2, int Oper);
  46.  
  47. #ifdef __MSDOS__
  48. static void cdecl BooleanFPE(int Sig, int Type, int *RegList);
  49. #else
  50. static void BooleanFPE(int Type);
  51. #endif /* __MSDOS__ */
  52. static void SetBooleanOutputKind(void);
  53.  
  54. /*****************************************************************************
  55. *   Verify input for Booleans. Ret. NULL if OK, otherwise an obj to return.  *
  56. *****************************************************************************/
  57. static ObjectStruct *VerifyBooleanInput(ObjectStruct *PObj1,
  58.                     ObjectStruct *PObj2, int Oper)
  59. {
  60.     ObjectStruct *PObj;
  61.     PolygonStruct *Pl;
  62.  
  63.     BooleanOperation = Oper;
  64.  
  65.     SetBooleanOutputKind();
  66.  
  67.     if (!IS_POLY_OBJ(PObj1) || (PObj2 != NULL && !IS_POLY_OBJ(PObj2)))
  68.     FatalError("Boolean: operation on non polygonal object(s).\n");
  69.  
  70.     signal(SIGFPE, BooleanFPE);         /* Will trap floating point errors. */
  71.  
  72.     switch (Oper) {
  73.     case BOOL_OPER_OR:
  74.         if (IS_POLYLINE_OBJ(PObj1) && IS_POLYLINE_OBJ(PObj2)) {
  75.         if (PObj1 -> U.Pl.P == NULL)
  76.             PObj = CopyObject(NULL, PObj2, FALSE);
  77.         else {
  78.             PObj = CopyObject(NULL, PObj1, FALSE);
  79.             Pl = PObj -> U.Pl.P;
  80.             while (Pl -> Pnext) Pl = Pl -> Pnext;
  81.             Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl.P);
  82.         }
  83.             return PObj;
  84.         }
  85.     case BOOL_OPER_AND:
  86.     case BOOL_OPER_SUB:
  87.     case BOOL_OPER_CUT:
  88.     case BOOL_OPER_MERGE:
  89.     case BOOL_OPER_NEG:
  90.             if (IS_POLYLINE_OBJ(PObj1) ||
  91.         (PObj2 != NULL && IS_POLYLINE_OBJ(PObj2))) {
  92.                 WndwInputWindowPutStr(
  93.         "Boolean: illegal operation on mixed polygon/line geometric object(s).");
  94.         PObj = GenPolyObject("", NULL, NULL);
  95.         return PObj;
  96.             }
  97.  
  98.         if (Oper != BOOL_OPER_NEG) {
  99.             ConvexPolyObject(PObj1);/* Make sure all polygons are convex.*/
  100.             ConvexPolyObject(PObj2);
  101.         }
  102.  
  103.         return NULL;
  104.     default:
  105.             FatalError("Boolean: undefined Boolean operation.\n");
  106.             return NULL;                 /* Make warning silent. */
  107.     }
  108. }
  109.  
  110. /*****************************************************************************
  111. *   Perform a Boolean OR between two objects.                     *
  112. *****************************************************************************/
  113. ObjectStruct *BooleanOR(ObjectStruct *PObj1, ObjectStruct *PObj2)
  114. {
  115.     ObjectStruct *PObj;
  116.     PolygonStruct *Pl;
  117.  
  118.     if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_OR)) != NULL)
  119.     return PObj;
  120.     else {
  121.     if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
  122.         signal(SIGFPE, BooleanFPE);     /* Will trap floating point errors. */
  123.         if (BooleanOutputInterCurve)
  124.         PObj = BooleanLow1Out2(PObj1, PObj2);/* Ret intersection crv.*/
  125.         else
  126.         PObj = BooleanCombineTwoObjs(BooleanLow1Out2(PObj1, PObj2),
  127.                          BooleanLow1Out2(PObj2, PObj1));
  128.     }
  129.     else {
  130.         /* We gain control from fatal error long jump - usually we should*/
  131.         /* return empty object, but if error is No intersection between  */
  132.         /* the two objects, we assume they have no common volume and     */
  133.         /* return a new object consists of the concat. of all polygons!  */
  134.         if (FatalErrorType != FTL_BOOL_NO_INTER) {
  135.         PObj = GenPolyObject("", NULL, NULL);/* Return empty object. */
  136.         }
  137.         else {
  138.         if (PObj1 -> U.Pl.P == NULL)
  139.             PObj = CopyObject(NULL, PObj2, FALSE);
  140.         else {
  141.             PObj = CopyObject(NULL, PObj1, FALSE);/* Copy Obj1 polys.*/
  142.             Pl = PObj -> U.Pl.P;
  143.             while (Pl -> Pnext) Pl = Pl -> Pnext;
  144.             Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl.P);/*Obj2 poly.*/
  145.         }
  146.         }
  147.     }
  148.     }
  149.  
  150.     signal(SIGFPE, DefaultFPEHandler);                /* Default FPE trapping. */
  151.  
  152.     SetObjectColor(PObj, BooleanOutputInterCurve ?
  153.              GlblICrvColor :
  154.              GlblBoolColor);       /* Default bool object color. */
  155.  
  156.     return PObj;
  157. }
  158.  
  159. /*****************************************************************************
  160. *   Perform a Boolean AND between two objects.                     *
  161. *****************************************************************************/
  162. ObjectStruct *BooleanAND(ObjectStruct *PObj1, ObjectStruct *PObj2)
  163. {
  164.     ObjectStruct *PObj;
  165.  
  166.     if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_AND)) != NULL)
  167.     return PObj;
  168.     else {
  169.     if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
  170.         signal(SIGFPE, BooleanFPE);     /* Will trap floating point errors. */
  171.         if (BooleanOutputInterCurve)
  172.         PObj = BooleanLow1In2(PObj1, PObj2);/* Ret intersection crv. */
  173.         else
  174.         PObj = BooleanCombineTwoObjs(BooleanLow1In2(PObj1, PObj2),
  175.                          BooleanLow1In2(PObj2, PObj1));
  176.     }
  177.     else {/* We gain control from fatal error long jump - ret empty obj. */
  178.         PObj = GenPolyObject("", NULL, NULL);
  179.     }
  180.     }
  181.  
  182.     signal(SIGFPE, DefaultFPEHandler);            /* Default FPE trapping. */
  183.  
  184.     SetObjectColor(PObj, BooleanOutputInterCurve ?
  185.              GlblICrvColor :
  186.              GlblBoolColor);       /* Default bool object color. */
  187.  
  188.     return PObj;
  189. }
  190.  
  191. /*****************************************************************************
  192. *   Perform a Boolean SUBSTRACT between two objects (PObj1 - PObj2).         *
  193. *****************************************************************************/
  194. ObjectStruct *BooleanSUB(ObjectStruct *PObj1, ObjectStruct *PObj2)
  195. {
  196.     ObjectStruct *PObj, *PTemp, *PTempRev;
  197.  
  198.     if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_SUB)) != NULL)
  199.     return PObj;
  200.     else {
  201.     if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
  202.         signal(SIGFPE, BooleanFPE);     /* Will trap floating point errors. */
  203.         /* The 1 in 2 must be reversed (the inside/outside orientation): */
  204.         if (BooleanOutputInterCurve) {
  205.         PObj = BooleanLow1In2(PObj2, PObj1);/* Ret intersection crv. */
  206.         }
  207.         else {
  208.         PTemp = BooleanLow1In2(PObj2, PObj1);
  209.         PTempRev = BooleanNEG(PTemp);
  210.         MyFree((char *) PTemp, ALLOC_OBJECT);
  211.  
  212.         PObj = BooleanCombineTwoObjs(BooleanLow1Out2(PObj1, PObj2),
  213.                          PTempRev);
  214.         }
  215.     }
  216.     else {/* We gain control from fatal error long jump - ret empty obj. */
  217.         PObj = GenPolyObject("", NULL, NULL);
  218.     }
  219.     }
  220.  
  221.     signal(SIGFPE, DefaultFPEHandler);                /* Default FPE trapping. */
  222.  
  223.     SetObjectColor(PObj, BooleanOutputInterCurve ?
  224.              GlblICrvColor :
  225.              GlblBoolColor);       /* Default bool object color. */
  226.  
  227.     return PObj;
  228. }
  229.  
  230. /*****************************************************************************
  231. *   Perform a Boolean CUT between two objects (PObj1 / PObj2).             *
  232. *****************************************************************************/
  233. ObjectStruct *BooleanCUT(ObjectStruct *PObj1, ObjectStruct *PObj2)
  234. {
  235.     ObjectStruct *PObj;
  236.  
  237.     if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_CUT)) != NULL)
  238.     return PObj;
  239.     else {
  240.     if (setjmp(LclLongJumpBuffer) == 0) { /* Its the setjmp itself call! */
  241.         signal(SIGFPE, BooleanFPE);     /* Will trap floating point errors. */
  242.         /* The 1 in 2 must be reversed (the inside/outside orientation): */
  243.         if (BooleanOutputInterCurve) {
  244.         PObj = BooleanLow1In2(PObj2, PObj1);/* Ret intersection crv. */
  245.         }
  246.         else {
  247.         PObj = BooleanLow1Out2(PObj1, PObj2);
  248.         }
  249.     }
  250.     else {/* We gain control from fatal error long jump - ret empty obj. */
  251.         PObj = GenPolyObject("", NULL, NULL);
  252.     }
  253.     }
  254.  
  255.     signal(SIGFPE, DefaultFPEHandler);                /* Default FPE trapping. */
  256.  
  257.     SetObjectColor(PObj, BooleanOutputInterCurve ?
  258.              GlblICrvColor :
  259.              GlblBoolColor);       /* Default bool object color. */
  260.  
  261.     return PObj;
  262. }
  263.  
  264. /*****************************************************************************
  265. *   Perform a Boolean MERGE between two objects.                 *
  266. *****************************************************************************/
  267. ObjectStruct *BooleanMERGE(ObjectStruct *PObj1, ObjectStruct *PObj2)
  268. {
  269.     ObjectStruct *PObj;
  270.     PolygonStruct *Pl;
  271.  
  272.     if ((PObj = VerifyBooleanInput(PObj1, PObj2, BOOL_OPER_MERGE)) != NULL)
  273.     return PObj;
  274.     else {
  275.     if (PObj1 -> U.Pl.P == NULL)
  276.             PObj = CopyObject(NULL, PObj2, FALSE);
  277.         else {
  278.             PObj = CopyObject(NULL, PObj1, FALSE);       /* Copy Obj1 polys. */
  279.         Pl = PObj -> U.Pl.P;
  280.         while (Pl -> Pnext) Pl = Pl -> Pnext;
  281.         Pl -> Pnext = CopyPolygonList(PObj2 -> U.Pl.P);   /* Obj2 polys. */
  282.     }
  283.     }
  284.  
  285.     SetObjectColor(PObj, GlblBoolColor);       /* Default bool object color. */
  286.  
  287.     return PObj;
  288. }
  289.  
  290. /*****************************************************************************
  291. *   Perform a Boolean NEGATION of given object PObj.                 *
  292. *  Negation is simply reversing the direction of the plane equation of each  *
  293. * polygon - the simplest Boolean operation...                     *
  294. *****************************************************************************/
  295. ObjectStruct *BooleanNEG(ObjectStruct *PObj)
  296. {
  297.     int i;
  298.     ObjectStruct *PTemp;
  299.     PolygonStruct *Pl;
  300.     VertexStruct *V;
  301.  
  302.     if ((PTemp = VerifyBooleanInput(PObj, NULL, BOOL_OPER_NEG)) != NULL)
  303.     return PTemp;
  304.     else {
  305.     PTemp = CopyObject(NULL, PObj, FALSE); /* Make fresh copy of object. */
  306.  
  307.     /* Scans all polygons and reverse plane equation and their vetrex    */
  308.     /* list (cross prod. of consecutive edges must be in normal dir.).   */
  309.     Pl = PTemp -> U.Pl.P;
  310.     while (Pl != NULL) {
  311.         for (i = 0; i < 4; i++) Pl -> Plane[i] = (-Pl -> Plane[i]);
  312.         RST_CONVEX_POLY(Pl);
  313.  
  314.         /* Invert vertices normals as well. */
  315.         V = Pl -> V;
  316.         do {
  317.         PT_SCALE(V -> Normal, -1.0);
  318.         V = V -> Pnext;
  319.         }
  320.         while (V != NULL && V != Pl -> V);
  321.  
  322.         Pl = Pl -> Pnext;
  323.     }
  324.     }
  325.  
  326.     signal(SIGFPE, DefaultFPEHandler);            /* Default FPE trapping. */
  327.  
  328.     SetObjectColor(PTemp, BooleanOutputInterCurve ?
  329.               GlblICrvColor :
  330.               GlblBoolColor);      /* Default bool object color. */
  331.  
  332.     return PTemp;
  333. }
  334.  
  335. /*****************************************************************************
  336. *   Combining two geometric objects, by simply concat. their polygon lists:  *
  337. *****************************************************************************/
  338. static ObjectStruct *BooleanCombineTwoObjs(ObjectStruct *PObj1,
  339.                        ObjectStruct *PObj2)
  340. {
  341.     PolygonStruct *Pl;
  342.  
  343.     CleanUpPolygonList(&PObj1 -> U.Pl.P);
  344.     CleanUpPolygonList(&PObj2 -> U.Pl.P);
  345.  
  346.     if (PObj2 == NULL)
  347.     return PObj1;
  348.     else {
  349.     if (PObj1 == NULL) return NULL;
  350.     Pl = PObj1 -> U.Pl.P;
  351.     while (Pl -> Pnext != NULL) Pl = Pl -> Pnext;
  352.     Pl -> Pnext = PObj2 -> U.Pl.P;/* Concat. the polygons into one list. */
  353.     PObj2 -> U.Pl.P = NULL;        /* And release the second object header. */
  354.     MyFree((char *) PObj2, ALLOC_OBJECT);
  355.     return PObj1;
  356.     }
  357. }
  358.  
  359. /*****************************************************************************
  360. *   Routine to clean up Boolean operation result polygons - delete zero      *
  361. * length edges, and polygons with less than 3 vertices.                 *
  362. *****************************************************************************/
  363. void CleanUpPolygonList(PolygonStruct **PPolygon)
  364. {
  365.     PolygonStruct *PPHead, *PPLast;
  366.     VertexStruct *PVHead, *PVTemp, *PVNext;
  367.  
  368.     PPLast = PPHead = (*PPolygon);
  369.  
  370.     while (PPHead != NULL) {
  371.     PVHead = PVTemp = PPHead -> V;
  372.     /* Look for zero length edges (V == V -> Pnext): */
  373.     do {
  374.         PVNext = PVTemp -> Pnext;
  375.         if (PT_EQ(PVTemp -> Pt, PVNext -> Pt)) {       /* Delete PVNext. */
  376.         PVTemp -> Pnext = PVTemp -> Pnext -> Pnext;
  377.         PVNext -> Pnext = NULL;            /* Free only PVNext. */
  378.         if (PVHead == PVNext) {          /* If we actually kill header. */
  379.             PPHead -> V = PVHead = PVTemp;
  380.             break;
  381.         }
  382.         MyFree((char *) PVNext, ALLOC_VERTEX);
  383.         }
  384.         else
  385.         PVTemp = PVTemp -> Pnext;
  386.     }
  387.     while (PVTemp != NULL && PVTemp != PVHead);
  388.  
  389.     /* Now test if at list 3 vertices in polygon, otherwise delete it:   */
  390.     if (PVHead == PVHead -> Pnext ||         /* One vertex only. */
  391.         PVHead == PVHead -> Pnext -> Pnext) {      /* Two vertices only. */
  392.         if (PPHead == (*PPolygon)) {
  393.         *PPolygon = (*PPolygon) -> Pnext;
  394.         PPHead -> Pnext = NULL;
  395.         MyFree((char *) PPHead, ALLOC_POLYGON);
  396.         PPHead = (*PPolygon);
  397.         }
  398.         else {
  399.         PPLast -> Pnext = PPHead -> Pnext;
  400.         PPHead -> Pnext = NULL;
  401.         MyFree((char *) PPHead, ALLOC_POLYGON);
  402.         PPHead = PPLast -> Pnext;
  403.         }
  404.     }
  405.     else {
  406.         PPLast = PPHead;
  407.         PPHead = PPHead -> Pnext;
  408.     }
  409.     }
  410. }
  411.  
  412. /*****************************************************************************
  413. *   Routine that is called from the floating point package in case of fatal  *
  414. * floating point error. Print error message, and quit the Boolean module.    *
  415. *****************************************************************************/
  416. #ifdef __MSDOS__
  417. static void cdecl BooleanFPE(int Sig, int Type, int *RegList)
  418. #else
  419. static void BooleanFPE(int Type)
  420. #endif /* __MSDOS__ */
  421. {
  422.     PrintFPError(Type);             /* Print the floating point error type. */
  423.  
  424.     FatalErrorType = FTL_BOOL_FPE;
  425.  
  426.     longjmp(LclLongJumpBuffer, 1);
  427. }
  428.  
  429. /*****************************************************************************
  430. *   Routine to select the output kind needed. Output of a Boolean operator   *
  431. * can be the real Boolean result model, or the intersection curves only.     *
  432. *****************************************************************************/
  433. static void SetBooleanOutputKind(void)
  434. {
  435.     ObjectStruct *PObj = GetObject("INTERCRV");
  436.  
  437.     if (PObj == NULL || !IS_NUM_OBJ(PObj)) {
  438.     WndwInputWindowPutStr("No numeric object name INTERCRV is defined");
  439.     BooleanOutputInterCurve = FALSE;
  440.     }
  441.     else
  442.     BooleanOutputInterCurve = !APX_EQ(PObj -> U.R, 0.0);
  443. }
  444.  
  445. /*****************************************************************************
  446. *   Routine that is called by the Boolean low level routines every small     *
  447. * amount of time (syncronically) to test if ^C/^Break was pressed and quit   *
  448. * if so. Note we could do it asyncronically, but this complicate thing too   *
  449. * much, and makes them highly unportable...                     *
  450. *****************************************************************************/
  451. void TestBooleanCtrlBrk(void)
  452. {
  453.     if (GlblWasCtrlBrk) {
  454.     WndwInputWindowPutStr("Control Break traps - Empty object result");
  455.  
  456.     FatalErrorType = FTL_BOOL_CTRL_BRK;
  457.  
  458.     longjmp(LclLongJumpBuffer, 1);
  459.     }
  460. }
  461.  
  462. /*****************************************************************************
  463. *   Routine that is called by the bool-low module in fatal cases errors.     *
  464. * Will print error message and long jump using LclLongJumpBuffer.         *
  465. *****************************************************************************/
  466. void FatalBooleanError(int ErrorType)
  467. {
  468.     char s[LINE_LEN_LONG];
  469.  
  470.     FatalErrorType = ErrorType;
  471.  
  472.     switch (ErrorType) {
  473.     case FTL_BOOL_NO_INTER:
  474.         /* If operation is union (OR), then if no intersection we assume */
  475.         /* the objects have no common volume and simply combine them!    */
  476.         if (BooleanOperation != BOOL_OPER_OR) {
  477.         sprintf(s, "Boolean: %s",
  478.             "Objects do not intersect - Empty object result");
  479.         WndwInputWindowPutStr(s);
  480.         }
  481.         break;
  482.     default:
  483.         sprintf(s, "Boolean: Undefined Fatal Error (%d !?)", ErrorType);
  484.         WndwInputWindowPutStr(s);
  485.         break;
  486.     }
  487.  
  488.     longjmp(LclLongJumpBuffer, 1);
  489. }
  490.